/**
 * Created by L.jp
 * Description:输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
 * 如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 * User: 86189
 * Date: 2023-02-03
 * Time: 22:30
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
  
  //某二叉树中任意节点的左右子树的深度相差不超过1
//这是对求二叉树的深度的扩展
public class Solution {
   /* //求树的深度
   //自顶向下遍历，每一个节点getdeepth会被重复调用多次，时间复杂度过高
    public int getDeepth(TreeNode root){
        if(root==null){
            return 0;
        }
        return Math.max(getDeepth(root.left),getDeepth(root.right))+1;
    }
    //左右子树的高度差小于等于1并且左右子树都是平衡二叉树才行
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return Math.abs(getDeepth(root.left)-getDeepth(root.right)) <=1
                && isBalanced(root.left)
                && isBalanced(root.right);
    
    }*/
    
      //自底向上遍历，先看左右子树是否平衡，再看当前节点为根节点的子树是否平衡、
      //如果左右子树的高度差小于等于1，那么就返回深度，否则返回-1表示子树不是平衡树
      public int getDeepth(TreeNode root){
          if(root==null){
              return 0;
          }
          //左子树高度
          int left=getDeepth(root.left);
          //右子树高度，如果左子树不平衡，那么右子树也没有必要求其深度
          int right=left==-1 ? -1 :getDeepth(root.right);
          //如果左子树不平衡或者右子树不平衡或者左右子树的高度差大于1，那么就返回-1
          if (left==-1 || right==-1 || Math.abs(left-right) >1){
              return -1;
          }else{
              //都平衡，就返回二叉树的深度
              return Math.max(left,right)+1;
          }
      }
      public boolean isBalanced(TreeNode root) {
          return getDeepth(root) !=-1;
      }
}
